package main

import "go-leetcode/leetcode/utils"

// 23. 合并 K 个升序链表
func main() {
	listNodes := []*utils.ListNode{
		utils.GetListNodeByArray([]int{1, 3, 5, 7, 8, 9}),
		utils.GetListNodeByArray([]int{2, 4, 6, 8, 10, 15}),
		utils.GetListNodeByArray([]int{5, 16, 20}),
	}

	println("转换为")

	node := mergeKLists(listNodes)
	pointResNode := node
	for pointResNode != nil {
		print(pointResNode.Val, " ")
		pointResNode = pointResNode.Next
	}
	return
}

func mergeKLists(lists []*utils.ListNode) *utils.ListNode {
	if len(lists) == 0 {
		return nil
	}
	if len(lists) == 1 {
		return lists[0]
	}

	start := 0
	mid := len(lists) / 2

	l1 := mergeKLists(lists[start:mid])
	l2 := mergeKLists(lists[mid:])

	return MergeTwoLists(l1, l2)
}

func MergeTwoLists(list1 *utils.ListNode, list2 *utils.ListNode) *utils.ListNode {
	dummy := &utils.ListNode{
		Val:  -1,
		Next: nil,
	}
	prev := dummy
	for list1 != nil && list2 != nil {
		if list1.Val < list2.Val {
			prev.Next = list1
			list1 = list1.Next
		} else {
			prev.Next = list2
			list2 = list2.Next
		}
		prev = prev.Next
	}

	if list1 != nil {
		prev.Next = list1
	} else if list2 != nil {
		prev.Next = list2
	}

	return dummy.Next
}

// 给你一个链表数组，每个链表都已经按升序排列。
//
//请你将所有链表合并到一个升序链表中，返回合并后的链表。
//
//
//
//示例 1：
//
//输入：lists = [[1,4,5],[1,3,4],[2,6]]
//输出：[1,1,2,3,4,4,5,6]
//解释：链表数组如下：
//[
//  1->4->5,
//  1->3->4,
//  2->6
//]
//将它们合并到一个有序链表中得到。
//1->1->2->3->4->4->5->6
//示例 2：
//
//输入：lists = []
//输出：[]
//示例 3：
//
//输入：lists = [[]]
//输出：[]
